#pragma once

#include <array>
#include <string>
#include <vector>

namespace solution_072
{

class Solution
{
public:
    int minDistance(std::string word1, std::string word2)
    {
        /* make #word1 >= #word2 */
        if (word1.size() < word2.size())
            word1.swap(word2);
        if (word2.empty())
            return word1.size();

        std::array lev{std::vector<int>(word2.size() + 1),
                       std::vector<int>(word2.size() + 1)};
        for (int i = 0; i <= (int)word2.size(); ++i)
            lev[0][i] = i;

        for (int row = 1; row <= (int)word1.size(); ++row) {
            lev[1][0] = row;
            for (int col = 1; col <= (int)word2.size(); ++col) {
                lev[1][col] = std::min( std::min(lev[0][col] + 1, lev[1][col-1] + 1),
                                        lev[0][col-1] + (word1.at(row-1) != word2.at(col-1)) );
            }
            lev.front().swap(lev.back());
        }

        return lev[0].back();
    }
};

}  /* namespace solution_072 */
